/*
 * @lc app=leetcode.cn id=106 lang=golang
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
	return build(inorder, postorder, 0, len(inorder)-1, 0, len(postorder)-1)
}

func build(in, post []int, in_start, in_end, post_start, post_end int) *TreeNode {
	// 终止条件
	if in_start > in_end {
		return nil
	}
	// 当前的根节点为后序遍历的最后的位置
	root := &TreeNode{Val: post[post_end]}
	in_root_pos := in_start
	// 在中序中查找当前根节点的位置
	for {
		if in[in_root_pos] != root.Val {
			in_root_pos++
			continue
		}
		break
	}

	// 右子树的长度
	right_size := in_end - in_root_pos

	root.Left = build(in, post, in_start, in_root_pos-1, post_start, post_end-right_size-1)
	root.Right = build(in, post, in_root_pos+1, in_end, post_end-right_size, post_end-1)
	return root
}

// @lc code=end

